L2-001 紧急救援

题目 L2-001 紧急救援

思路分析

最短路问题 同时需要维护很多额外信息：最短路有几条 该路径累积下来的救援人数有多少 以及具体路径

代码实现

#include<bits/stdc++.h>

using namespace std;

#define endl '\n'

using ll = long long;

using ull = unsigned long long;

using PII = pair<int,int>;

using Pll = pair<ll,ll>;

int dx[4]={-1,0,1,0},dy[4]={0,1,0,-1};

const int inf = 0x3f3f3f3f;

const int N=510;

int n,m,s,d;

int cityPeopleNum[N];

int g[N][N],dist[N],st[N],peopleNum[N],path[N],roadNum[N];

void dijkstra(){

	memset(dist,0x3f,sizeof dist);

	dist[s]=0;

	roadNum[s]=1;

	peopleNum[s]=cityPeopleNum[s];

	for(int i=0;i<n;i++){

		int choseCity=-1;

		for(int j=0;j<n;j++){ //找离该点最近的一个点

			if(!st[j] && (choseCity==-1 || dist[j]<dist[choseCity])){

				choseCity=j;

			}

		}

		st[choseCity]=true;

		for(int j=0;j<n;j++){ //以新点为中心 更新距离

			if(dist[j]>dist[choseCity]+g[choseCity][j]){  //如果更短直接更新

				dist[j]=dist[choseCity]+g[choseCity][j];

				peopleNum[j]=peopleNum[choseCity]+cityPeopleNum[j];

				path[j]=choseCity;

				roadNum[j]=roadNum[choseCity];

			}else if(dist[j] == dist[choseCity]+g[choseCity][j]){ //如果一样短 最短路数量+1

				roadNum[j]+=roadNum[choseCity];

				if(peopleNum[j]<peopleNum[choseCity]+cityPeopleNum[j]){ // 还需要看最短路中 哪条权最重

					peopleNum[j]=peopleNum[choseCity]+cityPeopleNum[j];

					path[j]=choseCity;

				}

			}

		}

	}

}

void print(int p){

	if(p==s){

		cout<<p;

		return;

	}

	print(path[p]);

	cout<<" "<<p;

}

int main()

{

	ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);

	memset(g,0x3f,sizeof g);

	cin>>n>>m>>s>>d;

	for(int i=0;i<n;i++)	cin>>cityPeopleNum[i];

	for(int i=0;i<m;i++){

		int x,y,z;cin>>x>>y>>z;

		g[x][y]=g[y][x]=min(g[x][y],z);

	}

	dijkstra();

	cout<<roadNum[d]<<" "<<peopleNum[d]<<endl;

	print(d);

	return 0;

 }

同类题型

视频讲解

⬅️ L2 🏠 00-天梯赛 ➡️ L2-002 链表去重